// 矩阵快速幂 && 快速递推
// https://soj.turingedu.cn/problem/50702/
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

template <typename T>
class Matrix {
  private:
    static const int mod = 1e9 + 7;
    int row;
    int col;

  public:
    vector<T> data;
    Matrix(int n, int m) : row(n), col(m), data(n * m) {} // 零矩阵
    Matrix(int I = 2) : row(I), col(I), data(I * I) {     // 单位矩阵
        for (int i = 0; i < I * I; i += I + 1) {
            data[i] = 1;
        }
    }
    T *operator[](int i) { return &data[0] + col * i; }
    const T *operator[](int i) const { return &data[0] + col * i; }

    Matrix operator*(const Matrix &b) const { // ret = a * b
        Matrix ret(row, b.col);
        for (int i = 0; i < ret.row; ++i)
            for (int j = 0; j < ret.col; ++j)
                for (int k = 0; k < col; ++k)
                    ret[i][j] = (ret[i][j] + (ll)(*this)[i][k] * b[k][j] % mod + mod) % mod;
        return ret;
    }

    Matrix pow(ll n) { // ret = a ^ n
        Matrix base = *this, ret(row);
        for (; n > 0; base = base * base, n >>= 1)
            if (n & 1) ret = ret * base;
        return ret;
    }

    void show() {
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j)
                cout << (*this)[i][j] << " ";
            puts("");
        }
    }
};

int main() {
    Matrix<int> ans(1, 2), base(2, 2);
    ans.data = vector<int>({0, 1}), base.data = {0, 1, 1, 1};
    // [f[i] f[i + 1]] = [f[i - 1] f[i]] * [{0, 1}, {1, 1}]
    int q;
    scanf("%d", &q);

    for (int i = 1; i <= q; ++i) {
        ll n;
        scanf("%lld", &n);
        printf("Case #%d: %d\n", i, (ans * base.pow(n))[0][0]);
    }

    return 0;
}
